package oj;

import java.util.HashMap;
import java.util.Map;

public class Num106 {
    /**
     * 通过中序和后序的遍历结果，还原一颗二叉树
     * @param inorder
     * @param postorder
     * @return
     */
    //存储中序遍历对应的值和索引
    Map<Integer,Integer> map=new HashMap<>();
    int index=0;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //将后序遍历结果反转,得到前序遍历的镜像结果
        int[] preorder=reverse(inorder,postorder);
        return buildTreeInternal(preorder,inorder,0,inorder.length);

    }
    public TreeNode buildTreeInternal(int[] preOrder, int[] inorder,int left,int right){
        if(left>=right){
            return null;
        }
        if(index>=preOrder.length){
            return null;
        }
        TreeNode root=new TreeNode(preOrder[index]);
        index++;
        int pos=map.get(root.val);
        root.right=buildTreeInternal(preOrder,inorder,pos+1,right);
        root.left=buildTreeInternal(preOrder,inorder,left,pos);
        return root;

    }
    public int[] reverse(int[] inorder,int[] postorder){
        int[] ret=new int[postorder.length];
        //将后序遍历结果反转称为前序遍历的镜像
        for (int i = 0; i < postorder.length; i++) {
            ret[i]=postorder[postorder.length-1-i];
        }
        for (int i = 0; i < inorder.length ; i++) {
            map.put(inorder[i],i);
        }
        return ret;
    }
}
